package leetcode;

//关于NumberOfIslands II,由于是逐个添加的，所以最好的方式是使用unionFind
//见hihocoder
public class NumberOfIslands {

	public static void main(String[] args) {
		char[][] grid = {{'1','1','1','1','0'},{'1','1','0','1','0'}};
		NumberOfIslands object = new NumberOfIslands();
		System.out.println(object.numIslands(grid));
	}
	
	//对于二维的来说，要怎样联合呢
	//显然我们需要一个m * n的数组来记录所有的状态
	//然后联合的时候我们可以使用对应一维下标的来进行联合
	private class UnionFind {

		private int count = 0;
		public int[] id = null;

		// 根据岛屿来完成初始化
		public UnionFind(int m, int n, char[][] grid) {
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					if (grid[i][j] == '1')
						count++;
				}
			}
			System.out.println("init count: " + count);
			id = new int[m * n];
			for (int i = 0; i < m * n; i++) {
				id[i] = i;
			}
		}

		public int count() {
			return count;
		}

		public boolean connected(int p, int q) {
			return find(p) == find(q);
		}

		//我们将同一组的指向同一个元素
		public int find(int p) {
			while(p != id[p]) {
		        id[p] = id[id[p]];
		        p = id[p];
		    }
		    return p;
		}

		public void union(int p, int q) {
			// 获得p和q的组号
			int pID = find(p);
			int qID = find(q);
			// 如果两个组号相等，直接返回
			if (pID == qID) {
				return;
			}
			id[pID] = qID;
			count--;
		}
	}

	// 说实话，没有什么思路
	// 后来看tag是使用并查集，才知道每当扫描一个的时候，如果上下左右中有1的话，就联合
	// 由于我们是从左往右，从上往下，所以我们只扫描左边或者上面的就可以了
	
	//虽然AC了，但是一看结果，11ms，beat 10%
	//看来这不是一个好方法
	public int numIslands(char[][] grid) {
		if(grid == null || grid[0] == null){
			return 0;
		}
		int m = grid.length;
		int n = grid[0].length;
		UnionFind unionFind = new UnionFind(m, n, grid);
		
		for(int i = 0; i < m; i++){
			for(int j = 0; j < n; j++){
				if(grid[i][j] != '1'){
					continue;
				}
				int p = i * n + j;
				if(j > 0 && grid[i][j - 1] == '1'){
					int q = p - 1;
					unionFind.union(p, q);
				}
				if(i > 0 && grid[i - 1][j] == '1'){
					int q = p - n;
					unionFind.union(p, q);
					
					//无意之间发现一个我不知道的点，外部类竟然可以访问内部类的私有变量
//					System.out.println("i :" + i + " j: " + j + "  count - 1 " + unionFind.count);
				}
			}
		}
		return unionFind.count();
	}
	
	//使用DFS来做
	//5ms
	public int numIslands2(char[][] grid) {
		if(grid == null || grid.length <= 0){
			return 0;
		}
	    int res = 0;
	    for (int i = 0; i < grid.length; i++) {
	        for (int j = 0; j < grid[0].length; j++) {
	            if (grid[i][j] == '1') {
	            	res++;
	                dfs(grid, i, j);
	            }
	        }
	    }
	    for (int i = 0; i < grid.length; i++) {
	        for (int j = 0; j < grid[0].length; j++) {
	            if (grid[i][j] == '#') {
	            	grid[i][j] = '1';
	            }
	        }
	    }
	    return res;
	}
	
	//DFS
	private void dfs(char[][] grid, int m, int n) {
	    if (m < 0 || m >= grid.length || n < 0 || n >= grid[0].length || grid[m][n] != '1') {
	        return;
	    }
	    grid[m][n] = '#';
	    dfs(grid, m+1, n);
	    dfs(grid, m-1, n);
	    dfs(grid, m, n+1);
	    dfs(grid, m, n-1);
	}
}
